package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : Rookie
 * @description : 给定一个值 输出和等于当前值的二叉树路径(到叶子节点)
 * @date : 2023/10/23
 */
public class TargetValuePath {

    public static void main(String[] args) {
        int[] input = {3, 27, 20, -1, -1, 15, 7};
        int target = 30;
        TreeNode root = BinaryTreeUtil.buildTree(input);
        List<Integer> path = new ArrayList<>();
        List<String> result = new ArrayList<>();
        traversal(root,target,path,result);
        System.out.println(result);
    }

    private static void traversal(TreeNode node,int target,List<Integer> path,List<String> result) {
        if (node == null) {
            return;
        }
        path.add(node.element);
        // 叶子节点
        if (node.left == null && node.right == null) {
            Integer sum = path.stream().reduce(Integer::sum).get();
            if (sum == target) {
                result.add(addArrow(path));
            }
            return;
        }

        //左
        if (node.left != null) {
            traversal(node.left,target,path,result);
            path.remove(path.size()-1);
        }
        //右
        if (node.right != null) {
            traversal(node.right,target,path,result);
            path.remove(path.size()-1);
        }
    }

    private static String addArrow(List<Integer> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size() - 1; i++) {
            sb.append(path.get(i)).append("->");
        }
        return sb.append(path.get(path.size() -1)).toString();
    }
}
